#include "Heap.h"

// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
    assert(hp);
    HPDataType* new=(HPDataType*)malloc(sizeof(HPDataType)*n);
    if(new==NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    hp->_a=new;
    memcpy(hp->_a,a,sizeof(HPDataType)*n);
    hp->_size=n;
    hp->_capacity=n;
    for(int i=(n-1-1)/2;i>=0;i--)
    {
        AdjustDown(hp->_a,n,i);
    }

}

// 堆的销毁
void HeapDestory(Heap* hp)
{
    assert(hp);
    free(hp->_a);
    hp->_size=hp->_capacity=0;
}

// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
    assert(hp);
    if(hp->_size==hp->_capacity)
    {
        int newcapacity=hp->_capacity==0?4:hp->_capacity*2;
        HPDataType* new=(HPDataType*)realloc(hp->_a,sizeof(HPDataType)* newcapacity);
        if(new==NULL)
        {
            perror("realloc fail");
            exit(-1);
        }
        hp->_a=new;
        hp->_capacity=newcapacity;
    }
        hp->_a[hp->_size]=x;
        hp->_size++;
    AdjustUp(hp->_a,hp->_size-1);
}

// 堆的删除
void HeapPop(Heap* hp)
{
    assert(hp);
    assert(hp->_size>0);
    Swap(&hp->_a[0],&hp->_a[hp->_size-1]);
    hp->_size--;
    AdjustDown(hp->_a,hp->_size,0);

}

// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
    assert(hp);
    return hp->_a[0];
}

// 堆的数据个数
int HeapSize(Heap* hp)
{
    assert(hp);
    return hp->_size;
}

// 堆的判空
int HeapEmpty(Heap* hp)
{
    assert(hp);
    return hp->_size==0;
}

//向下调整
void AdjustDown(HPDataType* a,int size,int parent)
{
    int child =(parent*2)+1;
    while(child<size)
    {
        if(child+1<size&&a[child+1]>a[child]) child++;
        
        if(a[child]>a[parent])
        {
            Swap(&a[child],&a[parent]);
            parent=child;
            child=(parent*2)+1;
        }
        else 
            break;
    }
}

//向上调整
void AdjustUp(HPDataType* a,int child)
{
    int parent =(child-1)/2;
    while(child>0)
    {
        if(a[child]>a[parent])
        {
            Swap(&a[child],&a[parent]);
            child=parent;
            parent=(child-1)/2;
        }
        else
            break;
    }
}

//交换
void Swap(int* a,int*b)
{
    int t=*a;
    *a=*b;
    *b=t;
}
// TopK问题：找出N个数里面最大/最小的前K个问题。
// 比如：未央区排名前10的泡馍，西安交通大学王者荣耀排名前10的韩信，全国排名前10的李白。等等问题都是Topk问题，
// 需要注意：
// 找最大的前K个，建立K个数的小堆
// 找最小的前K个，建立K个数的大堆
void Print(Heap* hp)
{
    for(int i=0;i<hp->_size;i++)
    {
        printf("%d ",hp->_a[i]);
    }
    printf("\n");
}
void PrintTopK(int* a, int size, int k)
{
    //升序 建大堆
    for (int i = (size - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, size, i);
	}
    size=size-1;
    while(size>0)
    {
        Swap(&a[0],&a[size]);
        AdjustDown(a,size,0);
        size--;
    } 
    for(int i=0;i<k;i++)
    printf("%d ",a[i]);
}

 